{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 量子近似优化算法\n",
    "\n",
    "\n",
    "`Linux` `CPU` `全流程` `初级` `中级` `高级`\n",
    "\n",
    "[![](https://gitee.com/mindspore/docs/raw/master/resource/_static/logo_source.png)](https://gitee.com/mindspore/mindquantum/blob/master/tutorials/5.quantum_approximate_optimization_algorithm.ipynb) [![](https://gitee.com/mindspore/mindquantum/raw/master/tutorials/images/view_mindquantum_api.png)](https://mindspore.cn/mindquantum/api/zh-CN/master/index.html)\n",
    "\n",
    "## 概述\n",
    "\n",
    "量子近似优化算法（Quantum Approximate Optimization Algorithm，QAOA）是利用量子计算机来近似解决组合优化问题的量子算法，最早由Farhi等人于2014年提出。在本教程里，我们将利用QAOA算法来解决最大割问题（Max-Cut），来熟悉MindQuantum中量子线路的搭建和训练。\n",
    "\n",
    "> 本文档适用于CPU环境。   \n",
    "> 你可以在这里找到完整的可运行的样例代码：<https://gitee.com/mindspore/mindquantum/blob/master/tutorials/source/quantum_approximate_optimization_algorithm.py>。\n",
    "\n",
    "## 环境准备\n",
    "\n",
    "本教程所需要的额外库：\n",
    "\n",
    "- networkx\n",
    "\n",
    "> `networkx`是创建、操作和研究复杂网络的结构、动态和功能库。可通过`pip3 install networkx`来进行安装。\n",
    "\n",
    "## Max-Cut问题描述\n",
    "\n",
    "Max-Cut问题是图论中的一个NP-complete问题，它需要将一个图中的顶点分成两部分，并使得两部分被切割的边最多。如下图（a），一个图由五个顶点构成，相互连接的边为```(0, 1), (0, 2), (1, 2), (2, 3), (3, 4), (0, 4)```。为了使得被切割的边最多，我们尝试通过（b）图的分割，将1、2、4分为一组，0、3分成另一组，因此可得到被切割的边有5条。当图中顶点增多时，我们很难找到有效的经典算法来解决Max-Cut问题。下面，我们介绍怎么将Max-Cut问题转化为一个哈密顿量的基态能力求解问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![max cut](./images/Max_Cut.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Max-Cut问题量子化\n",
    "\n",
    "这里我们将图中的每个顶点赋予一个量子比特，当顶点被分到左边时，我们将该顶点上的量子比特设置为$\\left|0\\right>$态，同理，右边为$\\left|1\\right>$态，当两个顶点被分到不同的集合中时，这两个顶点上的比特将处于不同的量子态。例如对于第0个顶点和第1个顶点，当其连线被切割是，两个顶点上的比特对应的量子态可以为$\\left|\\psi\\right>=\\left|0_11_0\\right>$或$\\left|\\psi\\right>=\\left|1_10_0\\right>$，其中下角标表示顶点的序号。此时，我们选择哈密顿量$H=(Z_1Z_0-1)/2$，这里$Z$为泡利$Z$算符。不难发现：\n",
    "$$\\left<\\psi\\right|H\\left|\\psi\\right>=-1$$\n",
    "而当顶点被分到同一集合中是，不难验证此时：\n",
    "$$\\left<\\psi\\right|H\\left|\\psi\\right>=0$$\n",
    "因此，我们只用按照上面的规则，写出图对应的哈密顿量$H$，利用量子计算机求得$H$的基态能量与基态，我们就可以得到该图的Max-Cut切割方案与最大切割边数。我们记所有边的集合为$C$，所有边个数为$c$，则哈密顿量可写为：\n",
    "$$H=\\sum_{(i,j)\\in C}(Z_iZ_j-1)/2$$\n",
    "\n",
    "## 导入相关依赖"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from mindquantum.core import Circuit, Hamiltonian, UN, H, ZZ, RX, QubitOperator\n",
    "from mindquantum.framework import MQAnsatzOnlyLayer\n",
    "from mindquantum.simulator import Simulator\n",
    "import networkx as nx\n",
    "import mindspore.nn as nn\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 搭建所需求解的图\n",
    "\n",
    "通过`add_path`可在图中添加边。最后画出图的结构。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8vihELAAAACXBIWXMAAAsTAAALEwEAmpwYAAA9FElEQVR4nO3deVjU1eIG8HfY3XAXTLSuIbKKCSLuXPW6Vi7gbt6fCyqgEKWkoGYqaC5lKriSCipJSmZa5oIiLoiAYQgoWC64Ai6AMgMD8/vD8Gaios5wZnk/z9Pz5DDznZd7k5dz5nzPkSgUCgWIiIh0hJ7oAERERNWJxUdERDqFxUdERDqFxUdERDqFxUdERDqFxUdERDqFxUdERDqFxUdERDqFxUdERDqFxUdERDrFQHQAUm95RTLsTM5B5q0CFEjlMDUxgLW5KYY6WaBhbWPR8YiIXpmEe3VSZVKv3Ufo0WzEXcwFAMjk5U++ZmKgBwUAt9aN4d3dEo7N64kJSUT0Glh89IytCZcR/HMmpPIyvOi/DokEMDHQR1B/a4xxfafa8hERvQlOddJTHpdeBopLy1/6XIUCKC4tQ/DPGQDA8iMijcARHz2Reu0+RmxIQHFp2TNfe5geh7w9SwEAdZw/RINek576eg1DfeyY5Io2FvWqIyoR0Wvjqk56IvRoNqTyZ0tPXpCHu7+GAXr6z32tVF6GsKPZqoxHRKQULD4C8Hj1ZtzF3Gc+01MoFMjf9xX06zREzdadnvt6hQI4ciEX+UUyFSclInozLD4CAOxMzqn08cIzP0Kak45GH0yHRN/ohdeQANiZUvl1iIjUBYuPAACZtwqeumUBAEpyL+Ne3BbU6zoGRmYtX3oNqbwcmTcLVRWRiEgpuKqTAAAFUvkzjz26cBIok0N69XfIrp1HyZ0/AQDFWadxz8AI9d3+r5LrlKo6KhHRG2HxEQDA1KSS/xQUCgAKSP9Ifuph+YPbkF3PfM51DFWQjohIeVh8BACwNjeFscGtp6Y763UdjXpdRz/5c97er/Ew7XCltzMAj3d0sW5ap1ryEhG9Ln7GRwAADyeLN76GAoBHuze/DhGRKvEGdnpiUmQSDmbcfuE2Zc+jKC+HhSQfv872QO3atZUfjohISTjioyd83CxhYvD8m9RfpIaRAZrknoWtrS1iYmLA36eISF2x+OgJx+b1ENDbEigreaXX1TDUw+wBNvgh/BtERkZizpw5GDBgAC5duqSipEREr4/FR085ueVLvJ2fBBNDPUgkL36uRPJ4j86g/jZPNqju3r07fvvtN/To0QMdOnTAvHnzIJVKVR+ciKiK+BkfPbFx40Z89dVXOH36NP588HjvzSMXciHB45vTK1Scx/fv1o3h7Wb53I2pr127Bn9/f/z2229YtWoV+vXrVy3fBxHRi7D4CABw5swZ9O/fH/Hx8bC2tn7yeH6RDDtTcpB5sxAF0lKYmhjCumkdeLSr+gns+/fvx9SpU+Ho6IgVK1agefPmqvo2iIheisVHyM3NhbOzM77++msMGTJEJe8hlUqxZMkSrFy5EgEBAfj4449hZPTivT+JiFSBxafj5HI5+vbtC2dnZyxevFjl73fp0iVMmzYNV65cQVhYGLp3767y9yQi+jsWn46bOXMmkpKSsH//fhgYVM9GPgqFArt378bHH3+Mbt26YenSpTA3N6+W9yYi4qpOHRYTE4OoqChERUVVW+kBgEQiweDBg5Geno5mzZrBwcEBq1evRlnZs4fgEhEpG0d8OiozMxNdu3bFzz//jPbt2wvNkp6eDh8fHzx48ABr1qxBhw4dhOYhIu3GEZ8OKiwsxODBg7Fo0SLhpQcAtra2iI2NxaefforBgwdj0qRJyM/PFx2LiLQUi0/HKBQKjBs3Dl27dsXEiRNFx3lCIpFg9OjRyMjIgImJCezs7BAeHo7y8vKXv5iI6BVwqlPHLFmyBDt37kR8fDyMjat2H54IZ8+ehZeXF/T09LBmzRo4OjqKjkREWoIjPh1y+PBhfP3119i1a5dalx4AvPfeezh58iTGjRuH3r174+OPP0ZBQYHoWESkBVh8OuLq1asYM2YMtm3bpjE7p+jp6cHT0xPnz5/Hw4cPYWNjg6ioKJ78QERvhFOdOkAqlaJbt27w8PBAQECA6Div7dSpU/Dy8kLDhg0RGhr61NZqRERVxRGfDvD19UWLFi0wY8YM0VHeSMeOHZGUlISBAweia9euCAwMxMOHD0XHIiINw+LTcuHh4YiPj8emTZsgedk5QxrAwMAAvr6+OHfuHK5cuQI7Ozv8+OOPnP4koirjVKcWS0pKQr9+/Z45cUGbxMbGwsfHB5aWlli5ciX+9a9/iY5ERGqOIz4tlZeXB3d3d6xdu1ZrSw8AevTogdTUVHTu3Bnt27fHggULIJPJRMciIjXG4tNCZWVlGDlyJEaMGAF3d3fRcVTOyMgIM2fORHJyMlJSUuDg4IADBw6IjkVEaopTnVpo1qxZSExMxK+//lqtm0+ri3379mHatGlPzhhs1qyZ6EhEpEY44tMyP/zwA7Zv347vvvtOJ0sPAAYMGIDz58/D2toajo6OWL58OUpLS0XHIiI1wRGfFlGnExfURVZWFqZOnYobN24gLCwMXbt2FR2JiARj8WmJwsJCdOjQAf7+/vD09BQdR60oFArs2rUL/v7+6NmzJ5YsWYImTZqIjkVEgnCqUwsoFAqMHz8enTp1YulVQiKRwMPDA+np6WjcuDHs7e2xZs0aHnxLpKM44tMCS5cuRXR0NOLj42FiYiI6jtpLS0uDt7c3iouLERYWxmlhIh3D4tNwsbGxGDVqFBITE9GiRQvRcTSGQqFAZGQkPvvsMwwaNAghISGoX7++6FhEVA041anBrl27htGjR2Pbtm0svVckkUgwduxYpKenQ09PD7a2tti8eTO3PiPSARzxaSiZTIZu3bphyJAh+Oyzz0TH0XhJSUnw9vaGsbExwsLC4ODgIDoSEakIR3waytfXFxYWFhp9zJA6cXZ2xqlTpzB69Gj07NkTn376KQoLC0XHIiIVYPFpoG+//RbHjh3TmhMX1IW+vj6mTJmCtLQ03L17F7a2toiOjub0J5GW4VSnhqk4ceHYsWOwsbERHUerHT9+HN7e3jA3N8fq1athZWUlOhIRKQFHfBokLy8PHh4eWLNmDUuvGnTp0gXJycno168fOnXqhDlz5uDRo0eiYxHRG2LxaYiKExeGDRsGDw8P0XF0hqGhIfz9/ZGamoqsrCzY2dlh7969omMR0RvgVKeGCAwMREJCAg4cOKCzm0+rg0OHDsHHxwc2Njb45ptv8Pbbb4uORESviCM+DbB7925s3bpVp09cUBe9evXCuXPn0L59ezg5OSEkJIQH3xJpGI741NyFCxfQtWtX7N27Fy4uLqLj0N/8+eef8PPzw8WLFxEaGoqePXuKjkREVcDiU2NFRUXo0KED/Pz8MGnSJNFx6Dn27NkDPz8/uLq6Yvny5XjrrbdERyKiF+BUp5qqOHHB1dWVJy6ouQ8//BDnz59Hy5Yt4ejoiBUrVkAul4uORUTPwRGfmlq+fDmioqJw/PhxnrigQTIzMzF16lTk5uZizZo16NSpk+hIRPQPLD41dOTIEYwcORKnT5/mqkENpFAoEB0djU8++QR9+/bF4sWL0bhxY9GxiOgvnOpUM9euXcOoUaOwdetWlp6GkkgkGD58ODIyMmBqago7OzusX78e5eXloqMRETjiUysVJy4MHjwYM2fOFB2HlCQ1NRXe3t6Qy+VYs2YN2rVrJzoSkU5j8amRKVOm4M6dO9i1axc3n9Yy5eXl2LJlC2bNmgUPDw8sXLgQ9erVEx2LSCdxqlNNbNq0CUePHsXmzZtZelpIT08P48aNQ3p6OuRyOWxsbLB161ae/EAkAEd8aiA5ORl9+/ZFXFwcbG1tRcehapCYmAgvLy/UqVMHoaGhsLOzEx2JSGdwxCdYfn4+PDw8EBYWxtLTIS4uLkhMTMTQoUPh5uaGgIAAFBUViY5FpBNYfAJVnLjg4eGBoUOHio5D1UxfXx8+Pj5IS0vDrVu3YGtri127dnH6k0jFONUpUFBQEE6dOsUTFwgAEBcXB29vb7Ro0QKrVq2CpaWl6EhEWokjPkF+/PFHREZG8sQFeqJ79+747bff0LNnT7i6umLevHkoLi4WHYtI67D4BLh48SI8PT3x/fffo0mTJqLjkBoxNDTE9OnTcfbsWaSlpcHe3h6//PKL6FhEWoVTndWs4sQFX19fTJ48WXQcUnP79+/H1KlTn2x+3bx5c9GRiDQeR3zVSKFQYMKECejQoQOPGaIq6du3L9LS0uDo6Ij33nsPX375JUpKSkTHItJoLL5q9PXXXyM7OxuhoaG8SZ2qzMTEBHPnzsXp06cRFxeHtm3b4ujRo6JjEWksTnVWk6NHj2LEiBFISEjAO++8IzoOaSiFQoHdu3fj448/RteuXbFs2TKYm5uLjkWkUTjiqwY5OTkYOXIkIiIiWHr0RiQSCQYPHoz09HRYWFjAwcEBq1at4sG3RK+AIz4Vk8lk6N69OwYOHIhZs2aJjkNaJj09HT4+Pnjw4AHCwsLg6uoqOhKR2mPxqZiXlxdu3bqFmJgYfq5HKqFQKLB9+3bMmDED77//PhYtWoSGDRuKjkWktjjVqUKbN29GbGwstmzZwtIjlZFIJBg9ejQyMjJgYmICW1tbhIeH8+BboufgiE9FUlJS0KdPH564QNXu7Nmz8PLygp6eHsLCwtC2bVvRkYjUCkd8KpCfnw93d3eeuEBCvPfeezh58iTGjRuHPn36wM/PDw8ePBAdi0htsPiUrKysDKNGjYK7uztPXCBh9PT04OnpifPnz+PRo0ewtbVFVFQUT34gAqc6lW727Nk4ceIEDh48yM2nSW2cOnUKXl5eaNCgAUJDQ2FjYyM6EpEwHPEp0Y8//oiIiAjs2LGDpUdqpWPHjkhKSsKgQYPQrVs3zJo1Cw8fPhQdi0gIFp+SVJy4EB0dzRMXSC0ZGBjA19cX586dw9WrV2FnZ4fdu3dz+pN0Dqc6laCoqAiurq6YOnUqpkyZIjoOUZXExsbCx8cH7777LlauXImWLVuKjkRULTjie0MKhQITJ05E+/btecwQaZQePXogNTUVXbp0gYuLCxYsWACpVCo6FpHKsfje0IoVK5CVlYWwsDDepE4ax8jICDNnzkRycjJSUlLg4OCAAwcOiI5FpFKc6nwDcXFxGDZsGE6fPs3Np0kr7Nu3D9OmTYOzszO++uorWFhYiI5EpHQc8b2m69evY+TIkYiMjGTpkdYYMGAAzp8/D2tra7Rt2xbLli1DaWmp6FhESsUR32uQyWRwc3PD+++/j6CgINFxiFQiKysLU6dOxfXr17FmzRp07dpVdCQipWDxvQZvb2/cuHEDMTEx0NPjoJm0l0KhwK5du+Dv748ePXpg6dKlvF2HNB5/ar+iLVu24PDhw9iyZQtLj7SeRCKBh4cH0tPT0aRJE9jb2yMsLAxlZWWioxG9No74XsHZs2fRu3dvHD16FHZ2dqLjEFW7tLQ0eHt749GjR1izZg3at28vOhLRK+OQpYry8/MxZMgQhIaGsvRIZ9nb2yMuLg6+vr748MMP4eXlhXv37omORfRKWHxVUFZWhtGjR2PIkCEYNmyY6DhEQkkkEowdOxbp6enQ09ODra0tNm/ezINvSWNwqrMK5syZg/j4eBw6dIibTxP9Q1JSEry9vWFsbIywsDA4ODiIjkT0QhzxvcSePXuwefNmnrhA9BzOzs44deoURo8ejZ49e+KTTz5BYWGh6FhEz8Xie4GsrCxMnDgR33//PczMzETHIVJb+vr6mDJlCs6fP4/79+/DxsYG0dHRPPmB1BKnOp/j4cOHcHV1hbe3N7y8vETHIdIox48fh7e3N8zMzBAaGgorKyvRkYie4IivEhUnLjg5OfGYIaLX0KVLFyQnJ6N///7o1KkTZs+ejUePHomORQSAxVepb775BhcuXMCaNWt44gLRazI0NIS/vz9SU1ORnZ0NOzs7/PTTT6JjEXGq85+OHTuGoUOHIiEhAf/6179ExyHSGocOHYKPjw+sra3xzTffcHN3EoYjvr+5ceMGRowYgYiICJYekZL16tUL586dg4uLC5ydnRESEgKZTCY6FukgFt9fSkpK4OHhAW9vb/Tp00d0HCKtZGxsjKCgIJw5cwYJCQlo06YNDh06JDoW6RhOdf5l6tSpuHr1Knbv3s3Np4mqyZ49e+Dr64uOHTti+fLleOutt0RHIh3An/AAIiIicODAAURGRrL0iKrRhx9+iPT0dLRs2RJt2rTBihUrIJfLRcciLafzI76KExeOHDkCe3t70XGIdNaFCxfg4+OD3NxchIWFoXPnzqIjkZbS6eHN3bt34e7ujtWrV7P0iARr3bo1Dh48iMDAQAwbNgzjx49Hbm6u6FikhXS2+CpOXBg0aBCGDx8uOg4R4fHJD8OHD0dGRgbq1asHOzs7rFu3jic/kFLp7FTn3LlzERcXh0OHDsHQ0FB0HCKqxLlz5+Dl5QW5XI6wsDA4OTmJjkRaQCdHfD/99BM2bdqE6Oholh6RGmvTpg3i4+MxZcoUDBgwAFOnTsX9+/dFxyINp3PFl52djQkTJiA6OponLhBpAD09PYwbNw7p6emQy+WwtbVFZGQkT36g16ZTU50VJy54eXnB29tbdBwieg2JiYnw8vJC7dq1ERYWBjs7O9GRSMPozIhPoVDA09MT7dq14zFDRBrMxcUFiYmJGDZsGNzc3DBjxgwUFRWJjkUaRGeKb+XKlcjIyMDatWt54gKRhtPX14ePjw/S0tJw+/Zt2NraYteuXZz+pCrRianO+Ph4eHh48MQFIi0VFxcHb29vNG/eHKtXr4alpeVLX5NXJMPO5Bxk3ipAgVQOUxMDWJubYqiTBRrWNq6G1CSK1hffjRs30L59e4SHh6Nv376i4xCRipSWluKbb77B4sWL4ePjg5kzZ6JGjRrPPC/12n2EHs1G3MXHN8fL5P+7R9DEQA8KAG6tG8O7uyUcm9erpvRUnbS6+EpKSvDvf/8bffv2xZw5c0THIaJqcO3aNfj7++Ps2bNYtWoV+vfv/+RrWxMuI/jnTEjlZXjRTz6JBDAx0EdQf2uMcX1H9aGpWml18U2bNg1XrlzhiQtEOujXX3/F1KlT4eDggBUrVuDYjXIE/5yB4tKq7wJTw1APQf1tWH5aRmuLLzIyEvPnz8eZM2dQr1490XGISACpVIolS5Zg9fafYDp4LuT/WM+nkJfgXuy3eJgZD0VJMYzM3kX9nhNh/FbrJ8+pYaiPHZNc0caiXjWnJ1XRyuL77bff8J///AexsbFwcHAQHYeIBBu9Ng4nLhcAkqeLL3//ahT9th+Gjd+GYaO38SgjHhIjEzSbshH6NesCeDzt2cfWDGvHOIuITiqgdfN/FScurFq1iqVHRMgrkiHp+qNnSq/s4X0UnTsESPRgNiIYjQcGoJadGxQlxShM3vvkeQoFcORCLvKLZNUdnVREq4qvvLwcY8aMwYcffogRI0aIjkNEamBnck6lj5fmXQXK5dA3bQz9WvUAAEbmj2+DKLnz51PPlQDYmVL5dUjzaFXxffHFF3j48CGWLFkiOgoRqYnMWwVP3bJQoezhPQCAnpHJk8ckf/17xdcqSOXlyLxZqMKUVJ0MRAdQlr179yI8PBxJSUk8cYGIniiQyit9XL9WfQBAeYn0yWOKv/694mtPX6dUBelIBK0Y8WVnZ2P8+PGIjo6Gubm56DhEpEZMTSr//d6wUXNAzwBlBblPRniymxcBAEZNnt3hydSEv1BrC40f8T18+BBDhgzB559/jk6dOomOQ0RqxtrcFMYGt56Z7tSvVR+1HXqiKPVX3I4KgmHjt/Eo4zgkRjVQx+n9p55rYqAH66Z1qjM2qZBG386gUCgwZswY6OvrY8uWLdx8moiekVckQ+cvYyv9nK+8VIZ7R77Fo4x4lJcUw9j8XdTvMQHGzWyeep6xgR5OftaDe3hqCY0e8a1atQrnz5/HyZMnWXpEVKlGtY3R3aoxDmbcfmabMj1DYzTs7YWGvZ9/VJlEAvy7dWOWnhbR2M/4jh8/juDgYMTExKBmzZqi4xCRGvNxs4SJgf5rvdbEQB/ebi8/7YE0h0YW382bNzF8+HBs3rwZLVu2FB2HiNScY/N6COpvDaNX7L7He3Vac7syLaNxxVdSUoKhQ4di8uTJ6Nevn+g4RKQheresCenJ7TDUU+Cln4woyqGnkHODai2lccU3ffp01K9fH7NnzxYdhYg0hFwux/Dhw/FRx3ewy6sL+tiawdhADyYGT/8INDHQg7GBHnq2bozSX5agWfGfz7kiaTKNWtW5detWzJs3D0lJSTxxgYiqbMaMGTh37hx+/vln6Os/nu/ML5JhZ0oOMm8WokBaClMTQ1g3rQOPdo9PYP/pp5/g7++Pc+fOcR2BltGY4ktNTUWvXr1w+PBhtGnTRnQcItIQ33//PQICApCUlISGDRu+0mtHjhwJCwsLLF26VEXpSASNKL579+7B2dkZCxYswKhRo0THISINkZ6eju7du+PXX39Fu3btXvn1d+7cgYODA/bt2wdnZx5LpC3U/jO+ihMXPvjgA5YeEVVZQUEBBg8ejCVLlrxW6QFAkyZNsHz5ckyYMAGlpdyrU1uo/Yhv3rx5iI2NxeHDh7n5NBFViUKhgLu7O5o0aYK1a9e+8bUGDBiAzp07IygoSEkJSSS1Lr59+/Zh8uTJSEpK4ubTRFRlixcvxu7duxEXFwdj4zffceXq1ato164d4uPjYWNj8/IXkFpT2+K7dOkSOnbsiN27d3PzaSKqskOHDuGjjz7CmTNnYGFhobTrhoaGIioqCseOHYOentp/SkQvoJb/7z169AhDhgzB3LlzWXpEVGVXrlzBmDFjsH37dqWWHgB4eT3ez3PNmjVKvS5VP7Ub8SkUCnz00UeQSCSIiIjg5tNEVCVSqRRdunTBiBEjMH36dJW8R2ZmJrp27Yrk5GS0aNFCJe9Bqqd2xbdq1SqEh4fj5MmTvGmUiKps4sSJKCgowI4dO1T6C3NwcDBOnDiBffv28RdzDaVWU53Hjx/HggULsGvXLpYeEVXZhg0bcPLkSYSHh6u8jAICAnD9+nVs27ZNpe9DqqM2I76bN2/C2dkZGzZsQP/+/UXHISINkZiYiAEDBuD48eNo3bp1tbxnUlISBgwYgN9//x1NmjSplvck5VGL4istLUWPHj3Qq1cvfP7556LjEJGGyM3NhbOzM1asWIHBgwdX63vPmDEDOTk5iIqKqtb3pTenFsXn5+eHS5cuYc+ePVwmTERVIpfL0adPH7i4uGDRokXV/v6PHj1CmzZt8PXXX+ODDz6o9ven16fy4ssrkmFncg4ybxWgQCqHqYkBrM1NMdTp8Q7o27dvx9y5c3HmzBnUr19flVGISIsEBATg7Nmz2L9//5MTF6rbkSNHMHbsWKSlpaFu3bpCMtCrU1nxpV67j9Cj2Yi7mAsAkMnLn3zNxEAPCgDvmRvhyOpZOLhjI09cIKIq27lzJ6ZPn46kpCQ0atRIaJZJkyZBX1+f9/dpEJUU39aEywj+ORNSeRleePXychjqS/D5h/Y85ZiIqiQjIwPdunXD/v374eTkJDoO7t+/D3t7e2zbtg3du3cXHYeqQOkfqD0uvQwUl76k9ABATw+lCgmCf87A1oTLyo5CRFqm4sSFL7/8Ui1KDwDq1auH0NBQeHp6ori4WHQcqgKljvhSr93HiA0JKC4te/JY3t6vIL38G8qKC6BnVBNG5pao3/2/MDJ/96nX1jDUx45JrmhjUU9ZcYhIiygUCnh4eKBRo0ZYt26d6DjPGDZsGN59910hC23o1Sh1xBd6NBtSedlTj8kf3IFxCwfUbvMf6NWoA+mfKbgTs/CZ10rlZQg7mq3MOESkRZYsWYKcnBysXLlSdJRKrVq1Ct9++y1SUlJER6GXMFDWhfKKZIi7mPvM9Kb56MVP/l12Kxu3Nn+MssJ8KMrkkOj/7+0VCuDIhVzkF8nQsPabHyNCRNrj8OHDWLFiBRITE5VyzJAqmJmZYcmSJZgwYQISExN5fqgaU9qIb2dyznO/VpD8E/J/DUPenqUAAFOXQU+VXgUJgJ0pz78OEemeq1evYvTo0di2bRuaN28uOs4LjR079smp7aS+lDbiy7xV8NQtC3/3KPMEZNfSAAD6dRrBuJltpc+TysuRebNQWZGISMNJpVK4u7vj008/RY8ePUTHeSmJRIJ169bB2dkZQ4YMgZWVlehIVAmljfgKpPLnfs189GK0mB6DxkNmo6zoLnJ3L4L8/u3nXKdUWZGISMNNmzYN77zzjsqOGVKFd955B3PmzMHEiRNRXl75YIDEUlrxmZo8O3gsL5VBUf54sYvEwAg1WjpBYmQClJdB/qDy4jM14bw4EQEbN27EiRMn8O2332rc8T9Tp05FaWkp1q9fLzoKVUJpU53W5qYwNrj11HRnyY0LyPtpGYyb20HPpDZk185DIXsEvZp1YWT27jPXMDHQg3XTOsqKREQa6syZM5g1axbi4+NRp47m/UzQ19fHxo0b4ebmhvfff1/pp8HTm1HaiM/D6dn/Y/XrNIRB/bcg/fM3FKUeRLm0CDWtu8BsZDD0TGo983x5WRnc32umrEhEpIFyc3Ph4eGBdevWwdraWnSc12ZnZ4dp06ZhypQpUIOzAOhvlHoD+6TIJBzMuP3yHVsqCwIF9G6mweziHoSEhMDNzU1ZsYhIQ8jlcvTt2xfOzs5YvHjxy1+g5kpKSuDk5ITAwECMHDlSdBz6i1JvYPdxs4SJwevtkm5iaICd8yfBx8cHEyZMQO/evZGUlKTMeESk5oKCggAACxc+u8mFJjIyMkJ4eDj8/f2Rl5cnOg79RanF59i8HoL6W6OG4atdtoahHoL6W+O9Fg0wevRoZGZmYsiQIRg4cCDc3d2Rnp6uzJhEpIZ27dqF7777DlFRUTAwUNryA+FcXFwwatQo+Pv7i45Cf1H6JtVjXN9BUH8b1DDUx8sWYkkkj/foDOpv89TpDIaGhpgyZQqysrLg6uoKNzc3/N///R8uX76s7LhEpAYyMjIwZcoU7Nq1C40bNxYdR+kWLFiAEydO4JdffhEdhaCC4gMel9+OSa7oY2sGYwM9mBg8/TYmBnowNtBDH1sz7Jjk+twjiWrWrIkZM2YgKysLLVq0gJOTE6ZNm4Zbt26pIjYRCVBYWIghQ4Zg8eLFcHZ2Fh1HJWrVqoX169djypQpKCzkJh2iqfwE9vwiGXam5CDzZiEKpKUwNTGEddM68Ghn8cp7ct65cweLFi1CREQEJk+ejBkzZvDUdiINplAoMHToUDRo0EAn7nkbP348atasidWrV4uOotNUXnyqcPXqVcyfPx8//vgjPvnkE/j6+qJWrWdvjyAi9bZkyRLs3LkT8fHxarv5tDLdu3cP9vb22LFjB7p06SI6js5SyVSnqrVo0QIbN27E8ePH8dtvv6FVq1YIDQ1FSUmJ6GhEVEWHDx/G119/jV27dulE6QFA/fr1sXLlSkycOBFSqVR0HJ2lkcVXoXXr1tixYwf27t2Lffv2oXXr1tiyZQvKyspe/mIiEubq1asYM2aMRpy4oGzu7u6ws7PTmls2NJFGTnU+T3x8PGbNmoW7d+9i4cKFGDx4sMbt8Uek7aRSKbp16wYPDw8EBASIjiPEzZs34ejoiIMHD8LR0VF0HJ2jVcUHPP6w/JdffkFgYCAMDQ0REhKCXr16sQCJ1MSkSZNw9+5dfP/99zr99/Lbb79FWFgYEhIStOq+RU2g0VOdlZFIJOjfvz9SUlIwffp0+Pj4oGfPnkhISBAdjUjnhYeHIz4+Hps2bdLp0gOAcePGoV69elixYoXoKDpH60Z8/1RaWootW7bgiy++QLt27bBw4UI4ODiIjkWkc5KSktCvXz/Ex8dr9ObTyvTHH3/AxcUFCQkJsLS0FB1HZ2jdiO+fDA0NMXHiRGRlZcHNzQ29evXCmDFjcOnSJdHRiHRGXl4e3N3dsXbtWpbe37Rs2RKBgYHw9PTkCQ7VSOuLr4KJiQn8/f2RnZ0NKysrdOjQAV5eXrhx44boaERaraysDCNHjsSIESPg7u4uOo7a8fPzw8OHD7Fx40bRUXSGzhRfhTp16mDu3LnIzMxE7dq1YW9vj4CAAOTn54uORqSVZs+ejfLycgQHB4uOopb09fURHh6OwMBAXL9+XXQcnaBzxVehUaNGWLp0KX7//XcUFBSgdevWWLBgAffRI1KimJgYbN++Hd999x1XLr6Ag4MDvLy84OPjwynPaqCzxVehWbNmWLt2LRISEpCZmYlWrVphxYoV3FWB6A1lZmZi8uTJ2Llzp1aeuKBsQUFBuHjxInbu3Ck6itbT+eKrYGlpiW3btuHAgQOIjY2FlZUVwsPDIZfLRUcj0jiFhYUYPHgwFi1ahPbt24uOoxGMjY0RHh4OX19ffvSiYlp/O8PrOnnyJAIDA3Hz5k0sWLAAHh4e0NPj7wlEL1Nx4kL9+vWxYcMG0XE0jp+fHx48eIDNmzeLjqK1WHwvoFAocPDgQQQGBj75cL5v3746f+Mt0YssXboU0dHRiI+Ph4mJieg4GqeoqAj29vZYt24d+vTpIzqOVmLxVYFCoUBMTAxmz56Nxo0bIyQkhEeKEFUiNjYWo0aNQmJiIlq0aCE6jsb69ddfMWXKFPz++++oXbu26Dhah8X3CuRyObZu3Yp58+bBzs4OwcHBaNu2rehYRGrh2rVrcHFxwdatW9GzZ0/RcTTef//7X9SvX59bmqkAi+81yGQyrF+/HiEhIejevTvmz58PKysr0bGIhJHJZOjWrRuGDBmCzz77THQcrZCfnw97e3vExMSgY8eOouNoFa7WeA3GxsaYNm0asrOz0aZNG3Tu3Bmenp64du2a6GhEQvj6+sLCwkJnjxlShYYNG+Kbb77BxIkTIZPJRMfRKiy+N1CrVi0EBgbi4sWLaNSoEdq2bYtPPvkEubm5oqMRVZtvv/0Wx44d44kLKjB06FBYWloiJCREdBStwqlOJbp58yaCg4MRFRWFqVOn4tNPP4WpqanoWEQqU3HiwrFjx2BjYyM6jla6fv062rZti9jYWJ4soyQc8SlR06ZNsXr1aiQlJeHy5cuwtLTEsmXLUFxcLDoakdLl5eXBw8MDa9asYempULNmzRAcHIyJEyeirKxMdBytwOJTgX/961/YsmULjhw5gpMnT6JVq1ZYt24dSktLRUcjUoqKExeGDRsGDw8P0XG03sSJE1GzZk2sXLlSdBStwKnOanDmzBkEBgbizz//xPz58zFixAjuAkMaLTAwEAkJCThw4AA3n64m2dnZcHV1RWJiIlq2bCk6jkZj8VWj2NhYBAYGori4GMHBwRgwYAAXA5DG+eGHH+Dn54ekpCQ0adJEdBydsnTpUvz66684ePAgf3a8ARZfNVMoFNizZw+CgoJgamqKkJAQuLm5iY5FVCWZmZno2rUr9u3bBxcXF9FxdI5cLoerqyu8vb0xfvx40XE0FotPkLKyMkRFRWHu3Llo1aoVgoOD4ezsLDoW0XMVFhaiQ4cO8Pf3h6enp+g4Ois1NRX/+c9/kJqaiqZNm4qOo5FYfIKVlJQgPDwcCxcuRMeOHbFgwQKukCO1o1AoMGzYMNStWxcbN24UHUfnBQUF4cKFCzy77zVxhYVgRkZG8PLyQlZWFlxcXNC9e3eMGzcOV65cER2N6Inly5fj8uXLWL16tegoBGDOnDlIS0tDTEyM6CgaicWnJmrWrImAgABkZWXBwsIC7dq1g6+vL27fvi06Gum4I0eOYNmyZdi5cyePGVITJiYm2LhxI6ZNm4Z79+6JjqNxWHxqpm7duliwYAEyMjKgp6cHW1tbBAUF4f79+6KjkQ66du0aRo0aha1bt+Ltt98WHYf+pkuXLhg0aBCmT58uOorGYfGpqSZNmmDFihU4e/Ysbt26hVatWmHx4sV4+PCh6GikI2QyGTw8PODn54devXqJjkOVWLRoEQ4dOoTDhw+LjqJRWHxqrkWLFggPD0d8fDxSUlLQqlUrhIaGoqSkRHQ00nJ+fn5o1qwZjxlSY6amplizZg08PT35S/ErYPFpCGtra0RHR2Pv3r3Yu3cvWrdujYiICO7dRyqxadMmHD16FJs3b+aN0mquf//+6NSpE+bOnSs6isbg7Qwa6tixYwgMDMS9e/ewcOFCDBo0iD+gSCmSk5PRt29fxMXFwdbWVnQcqoK8vDzY29tjz5493FigClh8GkyhUOCXX35BYGAgjIyMEBISws9i6I3k5+fD2dkZS5YswdChQ0XHoVcQFRWFkJAQJCcnw8jISHQctcbi0wLl5eWIjo7GnDlz0KJFC4SEhKBDhw6iY5GGKSsrQ79+/eDo6IilS5eKjkOvSKFQ4IMPPoCLiwunPV+CxadFSktLsWXLFnzxxRdwcnLCwoULYW9vLzoWaYigoCCcOnWKJy5osGvXrqFdu3acpn4JLm7RIoaGhpg4cSKysrLQvXt39OzZEx999BH++OMP0dFIze3evRuRkZH47rvvWHoarHnz5pg/fz4PrX0JFp8WMjExgb+/P7KystCqVSu4uLjA29sbN27cEB2N1NCFCxfg6emJ77//nscMaYHJkyfDwMAAoaGhoqOoLRafFjM1NcXcuXORmZmJmjVrwsHBAZ999hnu3r0rOhqpiaKiIgwZMgTBwcH8XFhL6OnpYcOGDZg/fz4uX74sOo5aYvHpgEaNGmHZsmVITU3F/fv3YWVlhYULF6KoqEh0NBJIoVBg/PjxcHV15TFDWqZ169b49NNPMXnyZHAZx7NYfDrEwsIC69atQ0JCAjIyMmBpaYlvvvkGMplMdDQS4KuvvsIff/yB0NBQ3gOqhaZPn447d+4gMjJSdBS1w1WdOuzcuXMICgrCuXPn8Pnnn2Ps2LFc2KAjjh49ihEjRuD06dPcfFqLpaSkoF+/fjh37hzMzMxEx1EbLD7CyZMnERgYiFu3bmHBggVwd3eHnh4nA7RVTk4O2rdvj4iICPznP/8RHYdUbObMmfjzzz+xY8cO0VHUBouPADz+vOfgwYMIDAyEQqFAcHAw+vTpwykwLSOTydC9e3cMHDgQs2bNEh2HqkFxcfGTTQkGDhwoOo5aYPHRUxQKBWJiYjB79mw0adIEISEh6Ny5s+hYpCReXl64desWYmJi+EuNDomLi8Po0aNx/vx51K1bV3Qc4Vh8VCm5XI7IyEjMmzcPDg4OCA4OhqOjo+hY9AY2b96MRYsW4cyZMzA1NRUdh6rZlClToFAosG7dOtFRhGPx0QvJZDKsX78eISEhcHNzw/z589GqVSvRsegVpaSkoE+fPtzKSoc9ePAA9vb2iIyMhJubm+g4QnEFA72QsbExpk2bhqysLDg4OKBTp06YNGkScnJyREejKsrPz4e7uzvCwsJYejqsbt26CAsLg6enJx49eiQ6jlAsPqqS2rVrIzAwEBcuXEDDhg3h6OiITz/9FLm5uaKj0QuUlZVh1KhRcHd35zFDhA8++ABOTk6YN2+e6ChCsfjolTRo0ACLFi1CWloapFIprK2tMW/ePBQUFIiORpX4/PPPUVJSgsWLF4uOQmpi5cqV2LJlC5KSkkRHEYbFR6+ladOmCA0NxZkzZ/DHH3+gVatWWL58OYqLi0VHo7/8+OOPiIiIwI4dO7gxAT3RpEkTLFu2DBMmTEBpaanoOEKw+OiNtGzZEhEREYiNjcWJEydgZWWF9evX6+xfKHVx8eJFeHp6Ijo6micu0DPGjBmDt956S2cPHOaqTlKqxMREBAUF4fLly5g/fz6GDx/OXWCqWVFRETp06ABfX19MnjxZdBxSU1euXIGTkxOOHz8Oa2tr0XGqFYuPVCI2NhazZs2CVCpFcHAwBgwYwBumq4FCocCIESNQq1YthIeH839zeqHVq1fju+++w7Fjx3TqF1QWH6mMQqHAnj17EBQUhLp16yIkJATdu3cXHUurffXVV9i2bRuOHz+OGjVqiI5Daq68vBxdu3bFqFGj4OPjIzpOtWHxkcqVlZUhKioKc+fOhZWVFYKDg+Hk5CQ6ltapOHEhISEB77zzjug4pCEyMjLQrVs3JCcno0WLFqLjVAvdGduSMPr6+hgzZgwyMzMxcOBAfPjhhxg6dCgyMzNFR9MaOTk5GDVqFCIiIlh69EpsbGzg5+f3ZEszXcDio2pjZGQELy8vZGVloX379ujWrRvGjx+PK1euiI6m0WQyGYYOHYqpU6eid+/eouOQBgoICMD169exfft20VGqBYuPql3NmjUREBCAixcvolmzZmjXrh38/Pxw+/Zt0dE0kr+/P8zMzDBz5kzRUUhDGRkZITw8XGd2Y2LxkTD16tXDggULkJ6eDolEAltbW8yePRv3798XHU1jbNmyBYcPH8aWLVt0alUeKZ+zszPGjBkDPz8/0VFUjn9TSDgzMzOsWLECKSkpuHnzJqysrPDll1/q/Ea6L3P27FlMnz4dMTExPGONlGL+/PlITEzE3r17RUdRKRYfqY23334b4eHhOHbsGJKTk9GqVSuEhYWhpKREdDS1k5+fjyFDhiA0NBR2dnai45CWqFmzJtavXw9vb2+t3n+XtzOQ2kpOTsbs2bNx4cIFfPHFFxg1ahT09fVFxxKurKwMAwYMgJ2dHZYvXy46DmkhT09PGBoaIiwsTHQUlWDxkdo7duwYZs2ahQcPHmDhwoUYOHCgTu9IMmfOHMTHx+PQoUPcfJpU4v79+7Czs0NUVBS6desmOo7SsfhIIygUCvz8888ICgqCsbExQkJC0LNnT9Gxqt2ePXvg4+ODpKQkmJmZiY5DWmz37t0ICAhAamqq1u0CxOIjjVJeXo7o6GjMmTMHb7/9NoKDg9GhQwfRsapFVlYWOnfujD179sDV1VV0HNIBQ4cOhaWlJRYtWiQ6ilKx+EgjlZaWYvPmzZg/fz6cnZ2xYMEC2Nvbi46lMkVFRXB1dYWPjw+8vLxExyEdcevWLTg6OmL//v147733RMdRGq7qJI1kaGgIT09PXLx4EV27dkXPnj0xduxY/PHHH6KjKZ1CocDEiRPRvn17TJkyRXQc0iHm5ub48ssvMWHCBMjlctFxlIbFRxqtRo0a+OSTT5CVlYV3330XLi4u8PHxwc2bN0VHU5oVK1YgKysLYWFhOr2oh8T473//i0aNGmnVCmJOdZJWycvLw+LFi7Fp0yZ4enoiICAADRo0EB3rtcXFxWHYsGE4ffo0N58mYS5fvgxnZ2ecPHkSVlZWouO8MY74SKs0atQIy5YtQ2pqKu7du4fWrVsjODgYRUVFoqO9suvXr2PkyJGIjIxk6ZFQ77zzDmbPng1PT0+Ul5eLjvPGWHyklSwsLLBu3TqcPHkS58+fR6tWrbBy5UrIZDLR0aqkpKQEHh4e8PHx4YkLpBamTZsGmUyGDRs2iI7yxjjVSTohNTUVs2fPxrlz5zBv3jx89NFHan3zt4+PD3JycvDDDz9w82lSG+fPn4ebmxvOnj0LCwsL0XFeG/9GkU5wdHTETz/9hO3bt2Pz5s1wcHDAzp071fLgzYiICBw8eBAREREsPVIrdnZ2mDp1Kry8vNTy705VccRHOkehUODAgQMIDAyERCJBcHAwevfurRYrJs+ePYvevXvjyJEjWn1fImmukpIStGvXDrNnz8aIESNEx3ktLD7SWQqFArt27cLs2bNhbm6OkJAQdOrUSVieu3fvwtnZGYsWLcLw4cOF5SB6mdOnT2PQoEH4/fff0ahRI9FxXhmLj3SeXC5HZGQk5s2bBwcHBwQHB8PR0bFaM5SVleH999+HjY0Nvvrqq2p9b6LX4e/vj7y8PERGRoqO8sr4AQLpPAMDA4wbNw4XL15E79690bdvX4waNQpZWVnVluGLL77Ao0eP8OWXX1bbexK9iYULF+LEiRPYv3+/6CivjMVH9BdjY2P4+voiKysLdnZ26NixIyZPnoycnByVvu9PP/2ETZs2ITo6GoaGhip9LyJlqVWrFtavX4/JkyejsLBQdJxXwqlOoue4e/culixZgg0bNmDcuHGYOXPmK3+ekVckw87kHGTeKkCBVA5TEwNYm5tiqJMFGtY2RnZ2Njp16oQff/wRHTt2VNF3QqQ648ePR61atbBq1SrRUaqMxUf0Ejdv3sTChQuxY8cOTJs2DZ988gnq1KnzwtekXruP0KPZiLuYCwCQyf+324WJgR4UALq82wCnNs7D1FEfwNvbW5XfApHK3Lt3D3Z2dvj+++/RuXNn0XGqhFOdRC/RtGlThIaGIjExEZcuXYKlpSW++uorFBcXV/r8rQmXMWJDAg5m3IZMXv5U6QGA9K/HDmfegbTzFNR5r391fBtEKlG/fn2sXLkSEydOhFQqFR2nSlh8RFXUsmVLRERE4PDhw4iPj4eVlRU2bNiA0tLSJ8/ZmnAZwT9noLi0DC+dS5HooVzPACG/ZGBrwmWVZidSJXd3d9jY2CA4OFh0lCrhVCfRa0pMTERgYCCuXr2K+fPno3Wn3hi1MRHFpWUAgPxfVkKWkwF5QS4k+oYwessK9f89HkaN337mWjUM9bFjkivaWNSr5u+CSDlu3LgBR0dHHD58GG3atBEd54VYfERv6PDhwwgMDMRdW3fIze1Q8RfqyuL3YfRWaxg1fhvFl1NR9uA29Os0RLPJGyAxMHrqGhIJ0MfWDGvHOFf/N0CkJOHh4Vi7di1OnTql1nvhsviIlCC3UIqOiw5BrvjftmfSnAyYWNgAAOT3b+P62gkAAPP/WwFjc8tnrmFsoIeTn/VAw9rG1ROaSMkUCgV69eqFfv36Yfr06aLjPBc/4yNSgl0p16Gvr//UYxWlBwCKcvnjf5HoQb925QfjSgDsTFHtPYNEqiSRSLB+/XosXrwY2dnZouM8F4uPSAkybxU8s3qzQnlJMfL3fQ0AMHUZBIPnFJ9UXo7Mm5p1IzDRP7377ruYNWsWJk2apLYnOLD4iJSgQCqv9PGyRw9wOyoQsuuZqO3YB/Xcxr3wOjfy7uH+/ftq+wODqCr8/PxQVFSE8PBw0VEqpb6fPhJpEFOTZ/8qyR/cwe0dcyC/ex2mrh6o7/Z/L71O4ok4tJg1ECUlJTAzM3vqH3Nz80r/XLduXbU4UomogoGBATZu3IhevXqhf//+eOutt0RHegoXtxApwdq4S/j60MWnpjtzVo9FWdFd6Js2Rk2r/21HVsu2O4zfav3MNUwM9OD/HytM7vYuiouLcfv2bdy6dQu3b99+8k9lfy4pKUGTJk2eW4x//zNLkqrTnDlzkJaWhpiYGLX6747FR6QEeUUydP4y9qniu7L4/Uqf27D/x6jdptczj7/uqs6KknxZUf69JF80gmRJkrLIZDK0bdsWCxYsgIeHh+g4T7D4iJRkUmQSDmbcfvmOLZWorvv4qlqSt2/fhkwmq1JJmpmZoV69eixJqtTJkyfh4eGBtLQ0NGhQ+cKu6sbiI1KS1Gv3MWJDwpOdW16FOu7c8veSfFlR/r0kX1aULEnd4+vri8LCQmzatEl0FAAsPiKl+t9enZXf2lCZGoZ6COpvgzGu76gumIr9syRfVJRSqbTKC3dYktqhqKgI9vb2WL9+PXr37i06DouPSNkel18mpPIXb1QtkQAmBvoI6m+t0aX3qoqLi3Hnzp1nPn98Xkm+bOEOS1Iz7N+/H15eXvj9999Ru3ZtoVlYfEQqcC7nPsKOZuPIhVxI8Pjm9AoV5/H9u3VjeLtZqtX0prqprCSfV5RVKcmKP7MkxRg7diwaNGiAFStWCM3B4iNSofwiGXam5CDzZiEKpKUwNTGEddM68GhnwT05layiJKuycKe4uLjKC3fq16/PklSS/Px82Nvb44cffoCrq6uwHCw+ItI5Uqm0ygt3/l6SLytKluTL7dixA/Pnz0dKSgqMjY2RVyTDzuQcZN4qQIFUDlMTA1ibm2Kok+p+OWTxERG9wD9L8kVF+c+SfFFR6mpJKhQKDBo0CM0du6Ck1b8RdzEXAJ66B7bi4wC31o3h3d0Sjs3rKTUDi4+ISEmkUmmVF+48evSoygt3tK0kV+1PxbJDl6BnaIwXFZCqFoCx+IiIBKisJJ9XlFUpyYo/q3tJqsMtPyw+IiI1V1GSVVm48/Dhwyov3GnQoEG1lmRlmzwUnPkRRecOojTvKqAoR93OI1Gv6+hnXqvMTR54OgMRkZozMTFBixYt0KJFi5c+9+8l+fdi/OOPP3Dq1KmnivLvJfmyolRGSYYezYZU/vTORiW3sqFnUhv6dRqhrODO878veRnCjmYrZVs/Fh8RkRZR15LMK5Ih7mLuM5s6NPrgUwDAnV0LUfyC4lMogCMXcpFfJHvj1Z4sPiIiHfUqJSmTySpd3VpRkn8vzn+WpJmZGe6aO0GOt/Em559LAOxMycHkbu++9jUAFh8REVWBsbHxK5XkPxfuRF02Qpn89UsPeLwDUubNwje6BsDiIyIiJTM2Nkbz5s3RvHnzJ4+d2HIG2ZnPn8qsqgJp6Rtf483ql4iIqApMTZQzzjI1MXzja3DER0REKmdtbgpjg1tP7dACAIWpv0J2LR0lty8BAB5lJUD+4A5qWrmiplXHp55rYqAH66Z13jgLR3xERKRyHk4WlT4uu5aOh2mHUVbweOuy0jt/4mHaYZTc/uOZ5yoAeLSr/DqvgjewExFRtZgUmYSDGbdfeE7l80gkQB9bM6Xcx8cRHxERVQsfN0uYGOi/1mtNDPTh7WaplBwsPiIiqhaOzeshqL81ahi+WvU83qvTWmmHNnNxCxERVZuKjaaDf86EVF72wmlPns5ARERa41zOfYQdzcaRC7mQ4PHN6RUqzuP7d+vG8HazVNpIrwKLj4iIhMkvkmFnSg4ybxaiQFoKUxNDWDetA492PIGdiIhIKbi4hYiIdAqLj4iIdAqLj4iIdAqLj4iIdAqLj4iIdAqLj4iIdAqLj4iIdAqLj4iIdAqLj4iIdMr/A2ICSgmCkVFGAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "g = nx.Graph()\n",
    "nx.add_path(g, [0,1])\n",
    "nx.add_path(g, [1,2])\n",
    "nx.add_path(g, [2,3])\n",
    "nx.add_path(g, [3,4])\n",
    "nx.add_path(g, [0,4])\n",
    "nx.add_path(g, [0,2])\n",
    "nx.draw(g,with_labels=True, font_weight='bold')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如上如，我们得到一个由5个节点和6条边构成的图结构。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 搭建QAOA量子线路\n",
    "\n",
    "### 线路搭建\n",
    "\n",
    "这里我们采用量子绝热近似算法，经过演化将量子态从$X^{\\otimes n}$的本征态演化到图多应哈密的量的基态。\n",
    "\n",
    "搭建图对应哈密顿量的含时演化线路："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_hc(g,para):\n",
    "    hc = Circuit()\n",
    "    for i in g.edges:\n",
    "        hc += ZZ(para).on(i)\n",
    "    return hc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "搭建$X^{\\otimes n}$含时演化的量子线路："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def build_hb(g, para):\n",
    "    hc = Circuit()\n",
    "    for i in g.nodes:\n",
    "        hc += RX(para).on(i)\n",
    "    return hc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为了使得最后优化的结果足够准确，我们需要将量子线路重复多次，因此我们通过如下函数搭建多层的训练网络："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_ansatz(g, p):\n",
    "    c = Circuit()\n",
    "    for i in range(p):\n",
    "        c += build_hc(g,f'g{i}')\n",
    "        c += build_hb(g,f'b{i}')\n",
    "    return c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "构建图对应的哈密顿量："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_ham(g):\n",
    "    hc = QubitOperator()\n",
    "    for i in g.edges:\n",
    "        hc += QubitOperator(f'Z{i[0]} Z{i[1]}')\n",
    "    return hc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 生成完整的量子线路和图所对应的哈密顿量\n",
    "\n",
    "这里我们选择`p = 4`，表示选用4曾的QAOA量子线路，`ansatz`是求解该问题的量子线路，`init_state_circ`是将量子态制备到均匀叠加态上的量子线路。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "p = 4\n",
    "ham = Hamiltonian(build_ham(g))\n",
    "ansatz = build_ansatz(g, p)\n",
    "init_state_circ = UN(H, g.nodes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 搭建待训练量子神经网络\n",
    "\n",
    "由于该问题不需要编码层量子线路，我们这里使用`MQAnsatzOnlyLayer`作为待训练的量子神经网络，并采用`Adam`优化器。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "import mindspore as ms\n",
    "ms.context.set_context(mode=ms.context.PYNATIVE_MODE, device_target=\"CPU\")\n",
    "\n",
    "circ = init_state_circ + ansatz\n",
    "sim = Simulator('projectq', circ.n_qubits)\n",
    "grad_ops = sim.get_expectation_with_grad(ham, circ)\n",
    "net = MQAnsatzOnlyLayer(grad_ops)\n",
    "opti = nn.Adam(net.trainable_params(), learning_rate=0.05)\n",
    "train_net = nn.TrainOneStepCell(net, opti)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 训练并展示结果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "train step: 0 , cut: [3.0000384]\n",
      "train step: 10 , cut: [3.0740116]\n",
      "train step: 20 , cut: [3.291378]\n",
      "train step: 30 , cut: [3.5130358]\n",
      "train step: 40 , cut: [3.7116692]\n",
      "train step: 50 , cut: [3.9258695]\n",
      "train step: 60 , cut: [4.06885]\n",
      "train step: 70 , cut: [4.1482286]\n",
      "train step: 80 , cut: [4.2075667]\n",
      "train step: 90 , cut: [4.2216697]\n",
      "train step: 100 , cut: [4.219716]\n",
      "train step: 110 , cut: [4.2484426]\n",
      "train step: 120 , cut: [4.310321]\n",
      "train step: 130 , cut: [4.3869066]\n",
      "train step: 140 , cut: [4.468603]\n",
      "train step: 150 , cut: [4.5552807]\n",
      "train step: 160 , cut: [4.6389103]\n",
      "train step: 170 , cut: [4.7030687]\n",
      "train step: 180 , cut: [4.7325706]\n",
      "train step: 190 , cut: [4.720634]\n",
      "train step: 200 , cut: [4.6801863]\n",
      "train step: 210 , cut: [4.641413]\n",
      "train step: 220 , cut: [4.630719]\n",
      "train step: 230 , cut: [4.6555276]\n",
      "train step: 240 , cut: [4.7030406]\n",
      "train step: 250 , cut: [4.7517853]\n",
      "train step: 260 , cut: [4.7854385]\n",
      "train step: 270 , cut: [4.8003826]\n",
      "train step: 280 , cut: [4.8025503]\n",
      "train step: 290 , cut: [4.800086]\n",
      "train step: 300 , cut: [4.7993703]\n",
      "train step: 310 , cut: [4.8025393]\n",
      "train step: 320 , cut: [4.8066764]\n",
      "train step: 330 , cut: [4.8070974]\n",
      "train step: 340 , cut: [4.8019547]\n",
      "train step: 350 , cut: [4.7941465]\n",
      "train step: 360 , cut: [4.7895412]\n",
      "train step: 370 , cut: [4.7927914]\n",
      "train step: 380 , cut: [4.8037663]\n",
      "train step: 390 , cut: [4.817476]\n",
      "train step: 400 , cut: [4.8274126]\n",
      "train step: 410 , cut: [4.830078]\n",
      "train step: 420 , cut: [4.8275557]\n",
      "train step: 430 , cut: [4.82526]\n",
      "train step: 440 , cut: [4.826516]\n",
      "train step: 450 , cut: [4.829952]\n",
      "train step: 460 , cut: [4.8320074]\n",
      "train step: 470 , cut: [4.831057]\n",
      "train step: 480 , cut: [4.8289337]\n",
      "train step: 490 , cut: [4.828836]\n",
      "train step: 500 , cut: [4.832123]\n",
      "train step: 510 , cut: [4.8371778]\n",
      "train step: 520 , cut: [4.8411226]\n",
      "train step: 530 , cut: [4.842478]\n",
      "train step: 540 , cut: [4.8421907]\n",
      "train step: 550 , cut: [4.8421745]\n",
      "train step: 560 , cut: [4.8431606]\n",
      "train step: 570 , cut: [4.844285]\n",
      "train step: 580 , cut: [4.8445735]\n",
      "train step: 590 , cut: [4.844259]\n"
     ]
    }
   ],
   "source": [
    "for i in range(600):\n",
    "    if i%10 == 0:\n",
    "        print(\"train step:\", i, \", cut:\", (len(g.edges)-train_net())/2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "根据上面的训练结果我们发现，该问题哈密顿量的基态能量对应的边切割数趋近与5。\n",
    "\n",
    "### 量子态展示\n",
    "\n",
    "前面我们通过训练得到了量子线路中参数的最优值，下面，我们通过`StateEvolution`类的`final_state`来输出量子线路在最优参数时的量子态，其中`ket`参数表示是否将最终量子态表示为右矢形式。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0.02090837256298316-0.013896610875073252j)¦00000⟩\n",
      "(0.012865120061967678+0.0036417563002864367j)¦00001⟩\n",
      "(0.024461651769855132+0.016082588541572487j)¦00010⟩\n",
      "(0.02665900288209095+0.028667026525713252j)¦00011⟩\n",
      "(0.012865120061967661+0.003641756300286507j)¦00100⟩\n",
      "(-0.13261220694607562+0.12131816696926725j)¦00101⟩\n",
      "(0.02665900288209106+0.028667026525713284j)¦00110⟩\n",
      "(0.0077605605960298545+0.013307014150508825j)¦00111⟩\n",
      "(-0.005108830641820924-0.016855682940484437j)¦01000⟩\n",
      "(0.2893552119928307+0.36375187206353543j)¦01001⟩\n",
      "(-0.05369567695690487+0.10854655574235807j)¦01010⟩\n",
      "(0.2893552119928306+0.36375187206353565j)¦01011⟩\n",
      "(0.012083509070472419+0.010521810302265303j)¦01100⟩\n",
      "(-0.05369567695690495+0.10854655574235811j)¦01101⟩\n",
      "(0.012083509070472474+0.010521810302265332j)¦01110⟩\n",
      "(-0.005108830641820898-0.016855682940484465j)¦01111⟩\n",
      "(-0.005108830641820921-0.016855682940484402j)¦10000⟩\n",
      "(0.012083509070472466+0.010521810302265334j)¦10001⟩\n",
      "(-0.05369567695690492+0.1085465557423581j)¦10010⟩\n",
      "(0.012083509070472504+0.01052181030226525j)¦10011⟩\n",
      "(0.2893552119928306+0.3637518720635356j)¦10100⟩\n",
      "(-0.053695676956904935+0.10854655574235816j)¦10101⟩\n",
      "(0.2893552119928306+0.3637518720635357j)¦10110⟩\n",
      "(-0.005108830641820899-0.016855682940484448j)¦10111⟩\n",
      "(0.007760560596029854+0.01330701415050879j)¦11000⟩\n",
      "(0.02665900288209102+0.028667026525713263j)¦11001⟩\n",
      "(-0.13261220694607564+0.1213181669692672j)¦11010⟩\n",
      "(0.012865120061967626+0.0036417563002865416j)¦11011⟩\n",
      "(0.02665900288209097+0.028667026525713308j)¦11100⟩\n",
      "(0.02446165176985506+0.01608258854157249j)¦11101⟩\n",
      "(0.012865120061967642+0.003641756300286466j)¦11110⟩\n",
      "(0.020908372562983193-0.013896610875073252j)¦11111⟩\n"
     ]
    }
   ],
   "source": [
    "pr = dict(zip(ansatz.params_name, net.weight.asnumpy()))\n",
    "print(circ.get_qs(pr=pr, ket=True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 概率图\n",
    "\n",
    "我们画出最终量子态在计算基矢下的概率分布"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXoAAAEMCAYAAADK231MAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8vihELAAAACXBIWXMAAAsTAAALEwEAmpwYAAAdw0lEQVR4nO3de7xcZXX/8c/KCRC580sOSiEQsAgNEhBjkLu8/AUDWCI/awuIKAUCP4ncL/HVarUWiz/FCxhJASkKQigINIUItFZUCkhCyw/ESptSWlKkBBAwIpfA6h/rGc7OZvbMPufMnJnz5Pt+veZ1zp5Zs55nnjmz9p5nX465OyIikq8Jve6AiIh0lwq9iEjmVOhFRDKnQi8ikjkVehGRzKnQi4hkbmKvO9DMlClTfNq0ab3uhojIuHHfffc95e6DzR7ry0I/bdo0li9f3utuiIiMG2b2H1WPaepGRCRzKvQiIplToRcRyZwKvYhI5lToRUQyp0IvIpI5FXoRkcyp0IuIZK4vT5iS/jNtwS0tH3/0/EN7kkuG6D2SKtqiFxHJnAq9iEjmVOhFRDKnQi8ikjkVehGRzKnQi4hkToVeRCRzKvQiIplToRcRyZwKvYhI5lToRUQyV6vQm9kcM3vYzFaY2YImj3/YzB5It7vMbLe6zxURke5qW+jNbABYCBwMTAeONLPppbB/Bw5w9xnA54BLhvFcERHpojpb9LOAFe7+iLu/DCwG5hYD3P0ud/9lWrwH2Kbuc0VEpLvqFPqtgccKyyvTfVWOA7433Oea2TwzW25my1etWlWjWyIiUkedQm9N7vOmgWYHEoX+3OE+190vcfeZ7j5zcHCwRrdERKSOOv94ZCUwtbC8DfB4OcjMZgCXAQe7+9PDea6IiHRPnS36ZcCOZra9ma0PHAEsKQaY2bbADcBH3P1fhvNcERHprrZb9O6+xszmA7cBA8Dl7v6QmZ2UHl8EfBqYDHzDzADWpGmYps/t0msREZEmav3PWHdfCiwt3beo8PvxwPF1nysiImNHZ8aKiGROhV5EJHMq9CIimVOhFxHJnAq9iEjmVOhFRDKnQi8ikjkVehGRzKnQi4hkToVeRCRzKvQiIplToRcRyZwKvYhI5lToRUQyp0IvIpI5FXoRkcyp0IuIZE6FXkQkcyr0IiKZU6EXEcmcCr2ISOZU6EVEMqdCLyKSORV6EZHMqdCLiGROhV5EJHMq9CIimVOhFxHJnAq9iEjmVOhFRDKnQi8ikjkVehGRzKnQi4hkToVeRCRzKvQiIplToRcRyZwKvYhI5lToRUQyp0IvIpK5WoXezOaY2cNmtsLMFjR5fGczu9vMXjKzs0qPPWpmD5rZ/Wa2vFMdFxGReia2CzCzAWAhMBtYCSwzsyXu/rNC2DPAKcAHKtIc6O5PjbKvIiIyAnW26GcBK9z9EXd/GVgMzC0GuPuT7r4MeKULfRQRkVGoU+i3Bh4rLK9M99XlwO1mdp+ZzasKMrN5ZrbczJavWrVqGOlFRKSVOoXemtznw2hjH3ffAzgYONnM9m8W5O6XuPtMd585ODg4jPQiItJKnUK/EphaWN4GeLxuA+7+ePr5JHAjMRUkIiJjpE6hXwbsaGbbm9n6wBHAkjrJzWwjM9uk8TtwEPDTkXZWRESGr+1RN+6+xszmA7cBA8Dl7v6QmZ2UHl9kZm8BlgObAq+Z2WnAdGAKcKOZNdq62t1v7corERGRptoWegB3XwosLd23qPD7E8SUTtnzwG6j6aCIiIyOzowVEcmcCr2ISOZU6EVEMqdCLyKSORV6EZHMqdCLiGROhV5EJHMq9CIimVOhFxHJnAq9iEjmVOhFRDKnQi8ikjkVehGRzKnQi4hkToVeRCRzKvQiIplToRcRyZwKvYhI5lToRUQyp0IvIpI5FXoRkcyp0IuIZE6FXkQkcyr0IiKZU6EXEcmcCr2ISOZU6EVEMqdCLyKSORV6EZHMqdCLiGROhV5EJHMq9CIimVOhFxHJnAq9iEjmVOhFRDKnQi8ikjkVehGRzKnQi4hkToVeRCRztQq9mc0xs4fNbIWZLWjy+M5mdreZvWRmZw3nuSIi0l1tC72ZDQALgYOB6cCRZja9FPYMcArwpRE8V0REuqjOFv0sYIW7P+LuLwOLgbnFAHd/0t2XAa8M97kiItJddQr91sBjheWV6b46aj/XzOaZ2XIzW75q1aqa6UVEpJ06hd6a3Oc189d+rrtf4u4z3X3m4OBgzfQiItJOnUK/EphaWN4GeLxm/tE8V0REOqBOoV8G7Ghm25vZ+sARwJKa+UfzXBER6YCJ7QLcfY2ZzQduAwaAy939ITM7KT2+yMzeAiwHNgVeM7PTgOnu/nyz53bptYiISBNtCz2Auy8FlpbuW1T4/QliWqbWc0VEZOzozFgRkcyp0IuIZE6FXkQkcyr0IiKZU6EXEcmcCr2ISOZU6EVEMqdCLyKSORV6EZHMqdCLiGROhV5EJHMq9CIimVOhFxHJnAq9iEjmVOhFRDKnQi8ikjkVehGRzKnQi4hkToVeRCRzKvQiIplToRcRyZwKvYhI5lToRUQyp0IvIpI5FXoRkcyp0IuIZE6FXkQkcyr0IiKZU6EXEcmcCr2ISOZU6EVEMqdCLyKSORV6EZHMqdCLiGROhV5EJHMq9CIimVOhFxHJnAq9iEjmVOhFRDJXq9Cb2Rwze9jMVpjZgiaPm5ldmB5/wMz2KDz2qJk9aGb3m9nyTnZeRETam9guwMwGgIXAbGAlsMzMlrj7zwphBwM7ptuewMXpZ8OB7v5Ux3otIiK11dminwWscPdH3P1lYDEwtxQzF/i2h3uAzc1sqw73VURERqBOod8aeKywvDLdVzfGgdvN7D4zm1fViJnNM7PlZrZ81apVNbolIiJ11Cn01uQ+H0bMPu6+BzG9c7KZ7d+sEXe/xN1nuvvMwcHBGt0SEZE66hT6lcDUwvI2wON1Y9y98fNJ4EZiKkhERMZInUK/DNjRzLY3s/WBI4AlpZglwDHp6Jt3A8+5+y/MbCMz2wTAzDYCDgJ+2sH+i4hIG22PunH3NWY2H7gNGAAud/eHzOyk9PgiYClwCLACeAE4Nj39zcCNZtZo62p3v7Xjr0JERCq1LfQA7r6UKObF+xYVfnfg5CbPewTYbZR9FBGRUdCZsSIimVOhFxHJnAq9iEjmVOhFRDKnQi8ikjkVehGRzKnQi4hkToVeRCRzKvQiIplToRcRyZwKvYhI5mpd60bGzrQFt1Q+9uj5h45hT0T6kz4jw6ctehGRzKnQi4hkToVeRCRzKvQiIplToRcRyZwKvYhI5lToRUQyp0IvIpI5FXoRkcyp0IuIZE6FXkQkcyr0IiKZU6EXEcmcCr2ISOZU6EVEMqdCLyKSOf3jEemosf6nEK3a61abndSL/usfd6x7tEUvIpI5FXoRkcyp0IuIZE6FXkQkcyr0IiKZU6EXEcmcCr2ISOZU6EVEMqdCLyKSORV6EZHM1Sr0ZjbHzB42sxVmtqDJ42ZmF6bHHzCzPeo+V0REuqttoTezAWAhcDAwHTjSzKaXwg4Gdky3ecDFw3iuiIh0UZ2Lms0CVrj7IwBmthiYC/ysEDMX+La7O3CPmW1uZlsB02o8t2/VveCULuQlMnr9eoG3HD5vFrW5RYDZ7wFz3P34tPwRYE93n1+IuRk4393vTMvfB84lCn3L5xZyzCO+DQDsBDw8upf2uinAUx2IGe+5etFmv+bqRZv9mqsXbfZrrl60WTdXHdu5+2DTR9y95Q34EHBZYfkjwEWlmFuAfQvL3wfeWee53b4ByzsRM95zjff+ayw0FuvyWIz2VmfqZiUwtbC8DfB4zZj1azxXRES6qM5RN8uAHc1sezNbHzgCWFKKWQIck46+eTfwnLv/ouZzRUSki9pu0bv7GjObD9wGDACXu/tDZnZSenwRsBQ4BFgBvAAc2+q5XXkl1S7pUMx4z9WLNvs1Vy/a7NdcvWizX3P1os26uUal7c5YEREZ33RmrIhI5lToRUQyp0IvIpK5db7Qm1nHxqBfc3U6n3INO5cp1/jP1el8ne5by7bWtZ2xZvY+YDdgNXCVuz9vZualgTCzHYAX3P2J8Zarbr51IVfdfF0Y/w3d/YXC8gR3f63Vc5Sr/3L1e9/qWqe26M1sf+Iia2uAGcAyM9vB3b24djWzucADxLkB242nXHXzrQu56ubrwvgfBtxscUXXTwKUP8xmto+Zvc/MJlXl6UWuuvnWhVx18/Ui17CNxem3/XIDzgT+X2H5s8BPiGtEQKz4Nge+CVxIfPhPBbYdL7lq5ttiHcjVq/fy7cBDxBVb30VcwO+rhccnAAcCrwE3AHOASRWvcUxzpZ9t860Lufr5vRzJrefFdyxvwGzgImCzwn1/CvwzsElangRMT7/vC1wJnAJsn+5rTHcdBHytTa71WuUqPO+g0far0bf0BzO7Vd+G0a9Grsq+9Wu/evhe/g7xQV0vLW8K/JD0oU55jgE+BnwcuIz48L+pyd/rzm1yTexUruH0rWauWn3r137VHP+evJcjqn2dSNLPN+JaO1uk3weBvwVOLMVcAnwC+F+kD3/hscaH+lTi7N45wMbAdsDfAcc3yfXh4h9WRa7tgN9LuTrWr/RY27616NcAcDSwTZsx+w5xtdF+61cv3stirt8Cvg28qxC7CbHSODMtTwbWT7+fBVwKHAq8iaGVzwTi2lB/CcxskWtKo1/lXKXX0rZf7fo2nH7V7Vu/9qtu33rxXo6oDo42QT/fgA8AdwO3A58jvjK9lZhnPRGYkuJuAv6duFTDZ4H3l/LsS1yhcwXwNPDb6f5ZwE+BEwq5bgR+UHjuQJNcS1Oel4Gvj7JfC4G7gN80+tWsb8BhwH3A/Bb9WpjG6xXgx1Vjlsb1ceLrZ9/0q0fv5ULg74Hngf3S/ScCPwKmFWKPB64HtuWNBeVs4kP9zvT7vMJj56b8xVyHAH/OUCGxilxfSP3btkW/DgAuT+9pq74dQKxA57Xo1wHAl4t9qujbh4mV6II+61fdMevFe/mJYq5h18JOFtZ+uhFF5EHg3cCuxFeim9Ob/lai2P4FcBXwEnHBtV2BjwJ/DRxZyDUL+BUxf3ZLqZ1ZwPeI/6r110Qxeg64uhAzUOrX08Cq9Ec84n6lfNcBr5bbLPXtu8TRJK8CNzfrV1r+Zur/kS3G7FvAM8B/EP9Epl/6NebvZVq+hdiJeyux9XcBcdXWc4iv5vsAHwT+m1g5fouYctqqlOdYYuXzGnBy6bEvEAViH+D3gReBe4mpg8a884RSrn9N/b+9Rb8mpde6Or1fV1T07aL0Hj0F7F7Rr0npPVhDWrlW9O1rqf8vAH/TR/2qO2a9eC+XA/9VfI3Droe9LsjduhE7z64n7dAANiMK6xJgD+Ir197AGcSHtBg3l9iam5Pu+wNii/IdwD8B15Ta2hbYi9g6/3i6b6044uu9AdunN23PNv06vUa/pgB3Amc0a7PQt9PSH/uOLfo1hfjg/V2bMTsI+Edglw706/Sa/VpSo191x+xDNd/Li2q8l1OAR4DT0v17AJ8nisT6wHHESurRFDcjxfwpcC3wlkLOs4lidDWxIXBIqV9nAosZ2kh4thFDqUAQK7iXGPqWVNWvm1OuUwpxa/WNWJE+nPK93mapX5cSxWt1oY9Vfft+ipveZ/2qO2a9eC+fJe0fGnE97HVB7uaNmEP9bmF5C2Je+VM14k4A/igtTwSmpt+NmGq4thA/ufD7li3itiy0d12Nfn2rSVy5X5MYmmqo7FubmEa/JtUZs5rjNanNWEwexnhNqhiLkY7Z1jXfy5ZjRsy9fpM0BZHunwqcR/zHNYiVwTXAeaWYzxJbjG8itubmAaenxw8npoIOLb22bYH/S8wdrxXDUGEwYqfedW36NZnY6LiySVyxb5OBrxCFrapfmxHnIPxhs/4X+jYB+AFr7xxt1q8diG9nrfo1BfhqjX7tDhzXpl/DGbOra7yXJzC08q/q21TgpJrv5YxR18LRJuinG3EkxsmFQd6M2GK8sBDzDuKr0ult4k4iDoc6pzHohccGiA/+pcQa/QfEzhOriLuW2CK4iChamxA7Zr5a6tcPWftolVZxO5Re+0BFmxemP0BrEtPo/x3AWcMYi1bjegZwaosxW5ra/SGFHVZN+jWfOPJgUo2xaDdmhxFbkpu0GK9Gm5ey9o60ZnFHEPO4k4hC8k/A7xc+nO8mttgaGwdVMVcSO+ka78/6hf59gJhiej+xRbkncaRG05jCeGyYfp8B3A98qNTm1cCbCzmq4q5sxJGOFKloc3dg01Zxqf+zgA1bjMXVaSw2aDNm32HosNdWYzGToQ2Fjo1ZzfGyOmPWJub1fnWkNnaj4PbiRuwYW0UUt38giup+xJbGpcROus2Jte/LxM6Nqrg5xBr258TX/ItS/omlNn9NzMN9mpiqeEMcMXXwGjEXN7vwhzCdmHu8MfXrghRzGUM7gmrHpZ8TW7VZjGnS/zpjcU/Nca0ai31Te6uJ6Z+qcX2BmHu9ZiRjUYo7ipjD/S9g1xZj0bTNiriXiB3NhxFF+hBiuuEPUswHiTnc5VUxKW4ZsaPvduLoii1K7Ta29B4h9oscVRHzFLFP4WfAYOlv7xZSsUz33Ulhi7RZHDF1dR9wUFouTyeU29yyRVyx/0fXHIt243pfi/F6ijgaaxWxAdMqru2YFcZi9nDGtWIsniU2OO4gfSOsGNfGhtBg8X0aVX3sdYHu2AuJLck/Sb9PIr5yXZDeqA2JD/5VwGPAxW3iXt/5kWL+jPiauFehvfcQc2xfL+RaK47Y8r2b2KF3QbptVyhIGxJHFlyb/gi+Rez4GU5cuSg1a3OtmBb9rzMWdce12ZgtBH4J7NIi5lCimP7lCMaiHHcl8W8unyCmH6rGolmbzeKOJlZmRxE7hpcQK7YZxDHPD6R2niDmck+uiPnjNI4vEUWjketU4K2F1/C29BqfJY7YeENM+nkr4ESBKx7lsQlRNBttXkzaCd0i7orUr+dJ3+BKbU1o0uYJzeIq+l93LOqMa7OxuJ6YHz+6alyHMWbFsTi35rhWjcVBxI7el4DPtBjXy4liP+rpmrXqY68LdMdeSEzb3Aq8LS1vQOxMWViImQT8bo24Q9IfQDnm64WYg4kdJc1yFeM+RhTJWekP+su88SSbDYit0E1HGDetFPfRJm2WY+YQ/6z9e23GYg6xldVuXA+tyFUciwXElkq7cd0/fZjajcXONeJ2BN5cYyyatVmOOxX4SWF5b+IwwfnE1M6uxM67x4DdWsR8gVg5Livk2ovYkvsEQydp/SGxwp7RImZP4N+IKbpDiCm1eaV+7wKcT/xNt4u7lTiE9eQU06xwzWrSZrO4j5X6X3cs6oxr1Vg8UGNc645ZeSzqjmuzsfhz4ki1j7cZ17vocJF3H+eFntihsQFxosp6xKFbx5EOdyIK0L3E/Hm7uPuJY2bb5TqzZq4TgI1K/d2TKGxfJtbyhwFbdShuu/QBKR/qVc71LtIZoMSOoAuIglJ+ncfVjakRd2zdmHTfhBb935OhHblt49rEFMeibty3icPiGtNkexMruEMKz28b0yauMWWyOfBXNWLeQkx1bEzsP1gEnNTk82Lt4ipiyielbVbRZjluC2JfRbvxGiC+TVXGtYkpjsVv1Yzbhvj8thqL9drFtIgrj8Xk1Gbbce1GrWz7P2P7lZkdSmwN3EVs4Z5NfFWfHw/bne7+czN7mDi88G1VccShWlsRb8CBbXKdDuxUI9dRwGwz+5S7Pwzg7j9J18janzg5Zyfig7DeKOPmEWfYDQB/a2Zntsi1PbGj5zl3f9zMfkzsMDMz+4fU/6dJF7xrFlMYi/ea2bXuvrpNrok1cs02s+tSrtfM4sqRFf3fHXi6Im4esbW2BTEn/3SbXI2xqGrz/hR3FHH46R1E4Xgy9f8uM7sXONvMfunud1fELAbOMLMXgdXufm+LXJ80s9Vp+daKXOeY2WvA8ykXxKAuJYr1AWZ2OLEvZQ1we4r7TZO4c4gi86y7f7EippHrVeC2Fm0elf4Of03sv7mT2FIt9/94M7vd3dcQUyj3NYm7CfiYmd1OTI00i1kMnGRmd7j7s2b2fJ04YjoJ4JWK/v/K3W+qiDmcOOpnlbvf5O6vtMn1a3e/ocV7tHEh5jm6oRtrj27e0gBNJU6Geg/xtfwc4mvdtsTe9guIKYLGiTbHtIi7h5gTe4bYMdjJXGcSO492KfX/MmKu99iUa0RxhbF4CvgFcQLRG3Kl2GuID8t/EsVw08JjHyBWmv+YXuMaYgdts5gfplxOfBXtdK6Ni2PQov9viCO2vF9Jt8+MJlf6/caU6zpix92F6f4FxL6FjxBTTU8A/1IVk5a/RMz1XtrhXDcB3yy915sC7yWOM3819b8qbgGxQ/tl4pjz0eT6E2Jfx2qGplg2Js5k/lKh/18jPiN7MXRU01pxwP9J789Shq4PM6JcTeImlN/vJv2fURHzXuLEqleJlf9oc91LFPddu1o3e124R9TpWEteQnwVagzc6ekPo3EtlP2I6ZPFbeIOIArOvl3KdQqxM7MxL70F8P+Js0K36UDcZGKr+X1tcq0gjsHegzgc9GTWLr6D6XlfJqaKqmL2A75IzL92K1ex8G7Qov/luN8ltuaP7ECuycSO4z8ufDDvBi5Py0cTh/o9Sazw31ERcxWx5f5sF3PdCVxf+oycQ2yZn1sVR3yO7k+vc/ooc00jLj3xIlGcZzI0dbIxsUK9gtgY+nX6ubgi7nqi+P2KmCcfTa6quPJ1kJr1f62YFPd5ho66Gm2us4mNslGdDFWrZva6aA+rszGFsTcxx3Yd6cy5wuMLiPm5GTXivkt8IxiLXOekP7jdUq43dyDuBmKaafPUfqtc7yQKV+MwuL2Irbf5xId2J+KU7I2rYtJ9u6dclXEdzLVxKa6q/xuX2pw6mlzpvo3Szz8ibREWxvUu4CuF5a/wxtPcyzG7EucrdDPXj4G/KCyfQWzFtou7mbTSGE0u4pvt14mV56eJo11mMnRcfOOokjnA3PR707iU6zjiEMRR5WoT11gpWGrz4ib9fz0m/TyPdPG7DuQ6G9hjTGrnWDTSkY7GV7mfE1tgX0l/eKsp7Bwh1qS314g7kdgqGstct9Xsf524E4mtsLq5/p4o+qcCm6fH90n3X0BMFzxBHKrYLOYIYprgudTmWOQaaZunjbLNzxJbzusRUwg/pXDdeWJu9jbg7Wn56IqY71I4G7JFXCdzXV8z7tYabY4k12aFxz5F7NN4V1o+rPBY0zhiP9puncjVizaHkWu3Ma+fY93giDoZH7prgX3S8hHEB/o6Yq7ydOIwuuOIebg5LeJ+h/inEv9MfI3vl1zdbvODxDTJeQydQLID8ZX8v4lvLs1itiXm/18AjhmjXL1q8xli7v57hb+9z5H2xaTl9zO0c7NpTLrvR8RX98VjkasXbVbkKp6F+inirNLr0rje0CLuDmJ/yLM0P6N1OLl60WbdXOcTh4BuOZY1dFz8z1gzW4/4+nOtu19hZgPEVMnbga2JKY4Xia/lvyF2FFXFvUxc2OpL7v5nfZSr221OIObEDwUedfdvmNl7iG8tn3H3z1fE7EfsGHxoDHP1os3ZxAkv5xFH2Wzg7kemv7/PEfsaLiMdj02cSfxKk5hvEEddnZVy7TQGuXrRZjnXi+5+dIrZwN1fSr//iDgC5gvEIcATy3FmthGxAplAFMzVI83VizaHkesOYqv/fe7+IGNpLNcqo7kRJ0QtYeia3wPEETAXMXStii1qxh3ep7nGos2jiB1/6xH7AT5aI+a3e5CrF23uTczzN6YuilesPJzYgXs18TW9VcxlxP6TsczVizbLua4qfWbfRlyv5n+XcjWLe5C4ZkwncvWizbq5dutJ/ex1Aa/d0TixZj5xtM3+hfvvoLBDo05cv+YawzZ/wNAhmm1jepGrV20W7p9MzI1fk5Z3IV1iYTgxvcjV4/5flZZ3J85DmDLcuE7m6kWbdXON5W3cnDDl7i+a2XeIY64/aWY7E4c5DRKHEtaO69dcY9jmlsSx97ViepGrV20W4p82sxOBL1qc0NWYIhtWTC9y9UH/f55iDnD3p4Yb18lcvWizbq4x1as1zEhvxCVPDySOYb0CeMdI4/o113jv/3gfi1L86cQRPZUntNSJ6UWu8d7/dWUsxuLW08ZH1fFYS07oRFy/5hrv/c9gLLYgLlhVeZGpOjG9yDXe+7+ujMVY3cbFUTcivWJmk9z9xdHG9CJXL9rs11y9aLNurrGgQi8ikrkJve6AiIh0lwq9iEjmVOhFRDKnQi8ikjkVehGRzKnQi4hk7n8A1B6Ge8mBtLMAAAAASUVORK5CYII=",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "def show_amp(state):\n",
    "    amp = np.abs(state)**2\n",
    "    n_qubits = int(np.log2(len(amp)))\n",
    "    labels = [bin(i)[2:].zfill(n_qubits) for i in range(len(amp))]\n",
    "    plt.bar(labels, amp)\n",
    "    plt.xticks(rotation=45)\n",
    "    plt.show()\n",
    "state = circ.get_qs(pr=pr)\n",
    "show_amp(state)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "根据概率分布图我们发现，该Max-Cut问题具有四个简并解，每个解对应的概率大概为25%。\n",
    "\n",
    "## 总结\n",
    "\n",
    "这里我们通过量子近似优化算法来解决了Max-Cut问题，并得到了案例中的图对应的最大切割方案。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 参考文献\n",
    "\n",
    "[1] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. [A Quantum Approximate Optimization Algorithm](https://arxiv.org/pdf/1411.4028.pdf)"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "5545a57ef4a1ac7dca167cae0bf17fda051fcd0639773c034bd7ce77ffd97d30"
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
